package mo.leetcode_top;

import java.util.Stack;

/**
 * 那么根据这道题的特点，我们需要按从高板子到低板子的顺序处理，先处理最高的板子，宽度为1，
 * 然后再处理旁边矮一些的板子，此时长度为2，因为之前的高板子可组成矮板子的矩形 ，
 * 因此我们需要一个递增栈，当遇到大的数字直接进栈，而当遇到小于栈顶元素的数字时，就要取出栈顶元素进行处理了，
 * 那取出的顺序就是从高板子到矮板子了，于是乎遇到的较小的数字只是一个触发，表示现在需要开始计算矩形面积了
 */
public class L84 {

    public int largestRectangleArea(int[] heights) {

        int res = 0;
        int[] dest = new int[heights.length+1];
        System.arraycopy(heights, 0, dest, 0, heights.length);
        dest[heights.length] = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < dest.length; i++) {
            while (!stack.isEmpty() && dest[stack.peek()] >= dest[i]) {
                int cur = stack.pop();
                res = Math.max(res, dest[cur] * (stack.isEmpty() ? i : (i - stack.peek() - 1)));
            }
            stack.push(i);
        }
        return res;
    }

    public static void main(String[] args) {
        L84 test = new L84();
        System.out.println(test.largestRectangleArea(new int[]{2,1,5,6,2,3}));
    }
}
